package com.cn.algorithm01;

/**
 * @author hels
 * @version 1.0
 * @date 2021/10/13 15:06
 * 使用双向链表结构实现双向队列
 * 双向队列：头尾都可实现增删值
 */
public class Code09_DoubleLinkedListToDeque {
    // 双向链表结构
    public static class Node<V> {
        private V value;
        private Node<V> last;
        private Node<V> next;

        public Node(V v) {
            value =  v;
            last = null;
            next = null;
        }
    }

    // 双向链表实现
    public static class MyDoubleQue<V> {
        private Node<V> head;
        private Node<V> tail;
        private int size;

        public MyDoubleQue() {
            head = null;
            tail = null;
            size = 0;
        }
        public boolean isEmpty() {
            return size == 0;
        }
        public int getSize() {
            return size;
        }

        // 头增加
        public void pushHead(V value) {
            // 首先创建一个数据节点
            Node<V> cur = new Node<V>(value);
            // 加入双向队列中
            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                cur.next = head;
                head.last = cur;
                head = cur;
            }
            size++;
        }
        // 尾部增加
        public void pushTail(V value) {
            Node<V> cur = new Node<V>(value);

            if (tail == null) {
                head = cur;
                tail = cur;
            } else {
                tail.next = cur;
                cur.last = tail;
                tail = cur;
            }
            size++;
        }

        // 弹出头部、
        public V pollHead() {
            V ans = null;
            if (head == null) {
                return ans;
            }

            ans = head.value;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                head = head.next;
                head.last = null;
            }
            size--;
            return ans;
        }
        // 弹出尾部
        public V pollTail() {
            V ans = null;

            if (tail == null) {
                return ans;
            }

            ans = tail.value;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                tail = tail.last;
                tail.next = null;
            }
            size--;
            return ans;
        }

        // 头/尾数据读取peek....
    }

}
